The problem of planning an optimized route via a plurality of points has been known for many years and there are many algorithms to find the best way according to one or more predefined criteria such as: shortest way, shortest time etc. The problem, also referred to as “Travelling Salesman”, is relevant when someone wishes to visit a many points in the same territory. The points can be different addresses in the same city, different cities in the same state or country and even different countries. The visits may be personal visits or delivering merchandize.
Planning a route connecting a small number of points (say up to about 10 points) may not be a too difficult task for an experienced person who knows the territory well, and it can usually be accomplished manually in a reasonable time frame using a map and simple logic. For example, one can select a starting point and then proceed to the next closest location and so on. Following this process carefully can produce an optimal route or a route which will be very close to it.
When it comes to planning a route with dozens or hundreds (or even more) points, one cannot solve this problem efficiently with manual solutions. A large number of points requires a computerized solution in order to produce an adequate solution.
The possible solutions depend on the number of points to be visited. For example, given 3 addresses to be visited, one can take 6 different routes. The number of different routes is calculated by calculating the permutations of 3 numbers (where repetition is not allowed). FIGS. 1A through 1F show 6 different routes traversing 3 different points, all starting from the same starting point. The distance traveled varies from route to route: 8.73 miles (FIG. 1A), 8.33 miles (FIG. 1B), 7.03 miles (FIG. 1C), 5.84 miles (FIG. 1D), 6.77 miles (FIG. 1E) and 6.79 miles (FIG. 1F). One can see that even in this simple example of starting from a given location and identifying the best route to cover 3 additional locations, the difference between the shortest route (5.84 miles, FIG. 1D) and the longest distance (8.73 miles, FIG. 1A) can be very significant and making the right or wrong selection may result in a significant savings (or loss) of resources.
The above example, considered only the distance covered. In reality, other considerations and preferences may also affect the selection of an optimal route, for example, the shortest time (calculating traffic speed at given times on given routes), the amount of time to be spent in each location (meetings, unloading or receiving merchandize), using or avoiding toll roads etc.
When considering travelling to 10 points, the number of permutations (10!=10*9*8*7*6*5*4*3*2) is 3,628,800. It is thus obvious that when dealing with a large number of points (dozens, hundreds, thousands), there is a huge number of possible routes. Sorting through all possible routes to find an optimal solution may take even a strong computer a long amount of time. In certain scenarios, for example, when a user requests a response online, the user expects to get a response back within a short delay such as under one minutes or under 3 or 5 minutes. There is thus a need to provide a route solution for travelling to a large number of points, within a short amount of time (under 5, 3 or 1 minute).
Too many possible solutions, cannot be performed in real-time.
Need to reduce # of possibilities.
Option #1, use clustering. Reduce 1,000 points to 100 by creating 10 clusters.